package com.LeetCode.why127;

import java.util.*;

/**
 * Created by Aqc on 2017/8/26.
 */
public class WordLadder {
    public static void main(String str[]) {
        String beginWord = "hit";
        String endWord = "cog";
        List<String> wordList = new ArrayList<>();

        wordList.add("hot");
        wordList.add("dot");
        wordList.add("dog");
        wordList.add("lot");
        wordList.add("log");
        wordList.add("cog");

        int result = ladderLength(beginWord, endWord, wordList);
        System.out.println(result);
    }

    private static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        /**
         小规模数应该是正确的，但没有通过LeetCode的检测

         做了很长时间，广度优先搜索（BFS）可以借助队列（queue）来完成！！
         */
        wordList.add(beginWord);
        int len = wordList.size();
        boolean[][] path = new boolean[len][len];
        for (boolean[] bl_ : path) {//初始化图
            for (boolean bl : bl_) {
                bl = false;
            }
        }
        //System.out.println(path[0][4]);
        int end = len;
        for (int i = 0; i < len; i++) {
            if (wordList.get(i).equals(endWord)) {
                end = i;
                break;
            }
        }
        int begin = len - 1;
//        for (int i = 0 ;i < len ;i++){
//            if (wordList.get(i) == beginWord){
//                begin = i;
//                break;
//            }
//        }

        for (int i = 0; i < len; i++) {//建立路径图
            for (int j = 0; j < len; j++) {
                if (i == j) continue;
                if (isDiffOneLetter(wordList.get(i), wordList.get(j))) {
                    path[i][j] = true;
                }
            }
        }
        int result = 0;
        HashSet<Integer> valueless = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(begin * 100);//后两位存放层数，即result
        result = LengthToEnd(path, end, queue, valueless);
        return result;
    }

    private static int LengthToEnd(boolean[][] path, int end, Queue<Integer> queue, HashSet<Integer> valueless) {
        int result = 0;
        while (queue.size() > 0) {
            int curBegin = queue.poll();
            result = curBegin % 100;
            curBegin = curBegin / 100;
            if (curBegin == end) {//找到路径
                return result + 1;
            }
            for (int i = 0; i < path.length; i++) {
                boolean tmp = path[curBegin][i];
                if (tmp == true && !valueless.contains(i)) {
                    valueless.add(curBegin);
                    int ad = i * 100 + result + 1;
                    queue.add(ad);
                }
            }
        }
        return 0;
    }

    private static boolean isDiffOneLetter(String first, String second) {
        int len = first.length();
        char[] fst = first.toCharArray();
        char[] snd = second.toCharArray();
        int sum = 0;
        for (int i = 0; i < len; i++) {
            if (fst[i] == snd[i]) sum++;
        }
        if (sum == len - 1) {
            return true;
        } else return false;
    }
}
